package com.mxw.leetcode.A8股票买卖;


/**
 * @author miao
 */
public class Demo1 {

    /**
     * 股票交易，交易次数为1
     *
     * @param prices
     * @return
     */
    int 股票交易1(int[] prices) {
        int n = prices.length;

        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++) {
            // base
            if (i - 1 == -1) {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 第二天卖出
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }

        return dp[n - 1][0];
    }


    /**
     * 可以同一天出售
     * @param prices
     * @return
     */
    int 股票交易2(int[] prices) {
        int n = prices.length;

        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++) {
            // base
            if (i - 1 == -1) {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 可以同一天出售
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return dp[n - 1][0];
    }


    /**
     * 冻结期1天
     *
     * @param prices
     * @return
     */
    int 股票交易3(int[] prices) {
        int n = prices.length;

        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++) {
            // base
            if (i - 1 == -1) {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            if (i - 2 == -1) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 可以同一天出售
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
        }

        return dp[n - 1][0];
    }


    /**
     * 含有手续费
     *
     * @param prices
     * @return
     */
    int 股票交易4(int[] prices) {
        int n = prices.length;
        int fee = 0;
        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++) {
            // base
            if (i - 1 == -1) {
                dp[i][0] = 0;
                dp[i][1] = -prices[i]-fee;
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0]-prices[i]-fee);
        }

        return dp[n - 1][0];
    }

    /**
     * 限制次数
     *
     * @param prices
     * @return
     */
    int 股票交易5(int[] prices) {
        int n = prices.length;
        int maxK = 0;
        int[][][] dp = new int[n][maxK+1][2];

        for (int i = 0; i < n; i++) {
            dp[i][0][0]=0;
            dp[i][0][1]=Integer.MIN_VALUE;
        }

        for (int i = 0; i < n; i++) {
            for (int k = maxK; k >=1; k--) {
                // base
                if (i - 1 == -1) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k-1][0]-prices[i]);
            }

        }

        return dp[n - 1][maxK][0];
    }

}
